Networking equipment such as routers includes routing tables which contain route information which is used by the routers to determine which output or egress port of the router a particular packet or message should be transmitted. A routing table contains a large number of entries for use by the router to determine how to forward packets that are received by the router. Conventional routing tables may contain hundreds of thousands of elements, and as a greater number of devices such as personal data assistants (PDAs), cell phones, and other devices are assigned IP addresses, the number of entries in a routing table is expected to grow substantially over the coming years. A route may have many paths associated therewith.
In a particular router, various processes (also known as “clients”) of the router have the ability to add or delete routes within a routing table of the router. If these clients of the routing table add or delete routes that depend on each other, then the routing table can contain loops with routes that depend on each other.
As recognized by the present inventors these loops can lead to incorrect forwarding behavior by the router; adversely affect notifications from the routing table to its clients; or cause route oscillations to occur between the routing table and its clients. In other words, when clients of a routing table resolve and add or delete routes with remote next hops to the routing table, it is possible that two or more routes depending on each other are installed, and these loops in the routing table may cause incorrect forwarding operations.
Accordingly, as recognized by the present inventors, what is needed is a process to detect and eliminate routing loops associated with recursive routes in a routing table, so as to provide a routing table that will be loop free. It is against this background that various embodiments of the present invention were developed.